#include<bits/stdc++.h>

using namespace std;
int a[100][100], n;
int dp[100][100];
int T, best;

int f(int x, int y) {
    if (dp[x][y] != 0)return dp[x][y];
    if (x == n - 1)return dp[x][y] = a[x][y];
    return dp[x][y] = a[x][y] + max(f(x + 1, y), f(x + 1, y + 1));

}

int main() {
    cin >> T;
    while (T--) {
        memset(a, sizeof(a), 0);
        memset(dp, sizeof(dp), 0);
        cin >> n;
        for (int i = 0; i < n; i++)for (int j = 0; j <= i; j++)cin >> a[i][j];
        cout << f(0, 0) << endl;
    }
    return 0;
}

